<!DOCTYPE html>
<html>

<head>
<meta charset="UTF-8">

<title> 【NOI2017】蚯蚓排队 - 题目 - Judge Duck Online </title>

<link rel="icon" type="image/png" href="/images/judgeduck-logo-small.png" />

<script src="/libs/js/jquery-3.2.1.min.js"></script>

<!-- Latest compiled and minified CSS -->
<link rel="stylesheet" href="/libs/css/bootstrap.min.css" />

<!-- Latest compiled and minified JavaScript -->
<script src="/libs/js/bootstrap.min.js"></script>

<link rel="stylesheet" type="text/css" href="/css/main.css" />
<link rel="stylesheet" href="/css/non-responsive.css" type="text/css" />

<script src="/js/md5.js"></script>
<script src="/js/judgeduck.js"></script>

<script type="text/x-mathjax-config">
	MathJax.Hub.Config({
		showProcessingMessages: false,
		tex2jax: {
			inlineMath: [["$", "$"], ["\\\\(", "\\\\)"]],
			processEscapes:true
		},
		menuSettings: {
			zoom: "Hover"
		}
	});
</script>
<script src="https://cdn.jsdelivr.net/npm/mathjax@2.7.1/MathJax.js?config=TeX-AMS_HTML"></script>

<link rel="stylesheet" href="https://cdn.jsdelivr.net/simplemde/latest/simplemde.min.css">
<script src="https://cdn.jsdelivr.net/simplemde/latest/simplemde.min.js"></script>

</head>

<body onload="">

<!-- Fixed navbar -->
<nav class="navbar navbar-default" role="navigation" style="background-color: #eeeeee">
	<div class="container">
		<div class="navbar-header">
			<div class="navbar-brand">
				<a href="/">
					<img src="/images/judgeduck-logo.png" width="40px" height="40px" style="margin:-10px" />
				</a>
			</div>
			<font class="navbar-brand">
				Judge Duck Online
			</font>
		</div>
		<div class="navbar-collapse collapse">
			<ul class="nav navbar-nav">
				<li class="nav-item">
					<a class="nav-link" href="/index/index.html"> 首页 </a>
				</li>
				<li class="nav-item">
					<a class="nav-link" href="/problems/index.html"> 题目列表 </a>
				</li>
				<li class="nav-item">
					<a class="nav-link" href="/submissions/index.html"> 提交记录 </a>
				</li>
				<li class="nav-item">
					<a class="nav-link" href="/blogs/index.html"> 博客 </a>
				</li>
				<li class="nav-item">
					<a class="nav-link" href="/faq/index.html"> FAQ </a>
				</li>
			</ul>
			<ul class="nav navbar-nav navbar-right">
				<li class="nav-item">
					<a class="nav-link" href="/user/login/index.html"> 登录 </a>
				</li>
				<li class="nav-item">
					<a class="nav-link" href="/user/register/index.html"> 注册 </a>
				</li>
			</ul>
		</div><!--/.nav-collapse -->
	</div>
</nav>




<div id="main_div" class="container" style="padding-left: 25px; padding-right: 25px">
<h2> 【NOI2017】蚯蚓排队 <a href='/problem/noi17b/board/index.html' class=' pull-right btn btn-success'> 排行榜 </a> </h2><hr />时间限制： 2 s <br />空间限制： 800 MB <br /><br /><h3>题目描述</h3>

<p>蚯蚓幼儿园有$n$只蚯蚓。幼儿园园长神刀手为了管理方便，时常让这些蚯蚓们列队表演。</p>

<p>所有蚯蚓用从 $1$ 到 $n$ 的连续正整数编号。每只蚯蚓的长度可以用一个正整数表示，根据入园要求，所有蚯蚓的长度都不超过 $6$ 。神刀手希望这些蚯蚓排成若干个队伍，初始时，每只蚯蚓各自排成一个仅有一只蚯蚓的队伍，该蚯蚓既在队首，也在队尾。</p>

<p>神刀手将会依次进行$m$次操作，每个操作都是以下三种操作中的一种：</p>

<ol>
<li><p>给出 $i$ 和 $j$ ，令 $i$ 号蚯蚓与 $j$ 号蚯蚓所在的两个队伍合并为一个队伍，具体来说，令 $j$ 号蚯蚓紧挨在 $i$ 号蚯蚓之后，其余蚯蚓保持队伍的前后关系不变。</p></li>
<li><p>给出 $i$ ，令 $i$ 号蚯蚓与紧挨其后的一只蚯蚓分离为两个队伍，具体来说，在分离之后， $i$ 号蚯蚓在其中一个队伍的队尾，原本紧挨其后的那一只蚯蚓在另一个队伍的队首，其余蚯蚓保持队伍的前后关系不变。</p></li>
<li><p>给出一个正整数 $k$ 和一个长度至少为 $k$ 的数字串 $s$ ，对于 $s$ 的每个长度为 $k$ 的连续子串 $t$ （这样的子串共有 $|s|-k+1$ 个，其中 $|s|$ 为 $s$ 的长度），定义函数 $f(t)$ ，询问所有这些$f(t)$的<strong>乘积</strong>对998244353取模后的结果。其中$f(t)$的定义如下：</p></li>
</ol>

<p>对于当前的蚯蚓队伍，定义某个蚯蚓的<strong>向后 $k$ 数字串</strong>为：从该蚯蚓出发，沿队伍的向后方向，寻找最近的 $k$ 只蚯蚓（包括其自身），将这些蚯蚓的长度视作字符连接而成的数字串；如果这样找到的蚯蚓不足 $k$ 只，则其没有<strong>向后$k$数字串</strong>。例如蚯蚓的队伍为 $10$ 号蚯蚓在队首，其后是 $22$ 号蚯蚓，其后是 $3$ 号蚯蚓（为队尾），这些蚯蚓的长度分别为 $4$ 、 $5$ 、 $6$ ，则 $10$ 号蚯蚓的<strong>向后 $3$ 数字串</strong>为<code>456</code>， $22$ 号蚯蚓没有<strong>向后 $3$ 数字串</strong>，但其<strong>向后 $2$ 数字串</strong>为<code>56</code>，其<strong>向后 $1$ 数字串</strong>为<code>5</code>。</p>

<p>而 $f(t)$ 表示所有蚯蚓中，<strong>向后 $k$ 数字串</strong>恰好为 $t$ 的蚯蚓只数。</p>

<h3>输入格式</h3>

<p>从标准输入读入数据。</p>

<p>输入文件的第一行有两个正整数 $n,m$ ，分别表示蚯蚓的只数与操作次数。</p>

<p>第二行包含 $n$ 个不超过 $6$ 的正整数，依次表示编号为 $1,2,\dots,n$ 的蚯蚓的长度。</p>

<p>接下来 $m$ 行，每行表示一个操作。每个操作的格式可以为：</p>

<ul>
<li><p><code>1</code> $i$ $j$（$1 \leq i, j \leq n$）表示：令 $i$ 号与 $j$ 号蚯蚓<strong>所在</strong>的两个队伍合并为一个队伍，新队伍中， $j$ 号蚯蚓紧挨在 $i$ 号蚯蚓之后。保证在此操作之前， $i$ 号蚯蚓在某个队伍的队尾， $j$ 号蚯蚓在某个队伍的队首，且两只蚯蚓不在同一个队伍中。</p></li>
<li><p><code>2</code> $i$（$1 \leq i \leq n$）表示：令 $i$ 号蚯蚓与紧挨其后一个蚯蚓分离为两个队伍。保证在此操作之前， $i$ 号蚯蚓不是某个队伍的队尾。</p></li>
<li><p><code>3</code> $s$ $k$（$k$为正整数，$s$为一个长度至少为$k$的数字串）表示：询问 $s$ 的每个长度为 $k$ 的子串 $t$ 的 $f(t)$ 的乘积，对998244353取模的结果。 $f(t)$ 的定义见题目描述。</p></li>
</ul>

<p>同一行输入的相邻两个元素之间，用恰好一个空格隔开。</p>

<p>输入文件可能较大，请不要使用过于缓慢的读入方式。</p>

<h3>输出格式</h3>

<p>输出到标准输出。</p>

<p>依次对于每个形如<code>3</code> $s$ $k$的操作，输出一行，仅包含一个整数，表示询问的结果。</p>

<h3>样例输入</h3>

<div class="row">
<div class="col-xs-12 form-group">
<textarea class="form-control" rows="12" style="background-color:white" readonly>5 9
3 1 3 5 3
3 333135 2
3 333135 1
1 1 3
1 2 5
1 3 2
1 5 4
3 333135 2
3 333135 1
3 333135 3
</textarea>
</div>

<p></div></p>

<h3>样例输出</h3>

<div class="row">
<div class="col-xs-12 form-group">
<textarea class="form-control" rows="6" style="background-color:white" readonly>0
81
1
81
0
</textarea>
</div>

<p></div></p>

<h3>样例解释</h3>

<p>第一次询问：由于每个队伍均只有一只蚯蚓，所以没有任何蚯蚓有<strong>向后2数字串</strong>，答案为 $f($<code>33</code>$) \times f($<code>33</code>$) \times f($<code>31</code>$) \times f($<code>13</code>$) \times f($<code>35</code>$) = 0 \times 0 \times 0 \times 0 \times 0 = 0$ 。</p>

<p>第二次询问：每个队伍仍只有一只蚯蚓，每只蚯蚓的<strong>向后1数字串</strong>就是将自己的长度视为字符的数字串，即：得到的5个<strong>向后1数字串</strong>为<code>1</code>、<code>3</code>、<code>3</code>、<code>3</code>、<code>5</code>（不分先后顺序，下同），答案为 $f($<code>3</code>$) \times f($<code>3</code>$) \times f($<code>3</code>$) \times f($<code>1</code>$) \times f($<code>3</code>$) \times f($<code>5</code>$) = 3 \times 3 \times 3 \times 1 \times 3 \times 1 = 81$ 。</p>

<p>接下来进行了若干次队伍的合并操作，使得所有蚯蚓合并成了一个队伍，这个队伍从前到后的蚯蚓依次为： $1$ 号蚯蚓（长度为 $3$ ）、$3$ 号蚯蚓（长度为 $3$ ）、$2$ 号蚯蚓（长度为 $1$ ）、$5$ 号蚯蚓（长度为 $3$ ）、$4$ 号蚯蚓（长度为 $5$ ）。</p>

<p>第三次询问： $4$ 号蚯蚓没有<strong>向后2数字串</strong>，而其他蚯蚓都有。得到的4个<strong>向后2数字串</strong>为<code>13</code>、<code>31</code>、<code>33</code>、<code>35</code>，答案为 $f($<code>33</code>$) \times f($<code>33</code>$) \times f($<code>31</code>$) \times f($<code>13</code>$) \times f($<code>35</code>$) = 1 \times 1 \times 1 \times 1 \times 1 = 1$。</p>

<p>第四次询问：虽然队伍的排列方式改变了，但是每只蚯蚓的<strong>向后1数字串</strong>没有发生改变，所以答案同第二次询问。</p>

<p>第五次询问： $4$ 号蚯蚓、 $5$号蚯蚓没有<strong>向后3数字串</strong>，而其他蚯蚓都有。得到的3个<strong>向后3数字串</strong>为<code>135</code>、<code>331</code>、<code>313</code>，答案为 $f($<code>333</code>$) \times f($<code>331</code>$) \times f($<code>313</code>$) \times f($<code>135</code>$) = 0 \times 1 \times 1 \times 1 = 0$。</p>

<h3>数据范围</h3>

<p>保证 $n \leq 2 \times 10^{5}$，$m \leq 5 \times 10^{5}$，$k \leq 50$ 。</p>

<p>设 $\sum |s|$ 为某个输入文件中所有询问的 $s$ 的长度总和，则 $\sum |s| \leq 10^{7}$  。</p>

<p>设 $c$ 为某个输入文件中形如 <code>2 i</code> 的操作的次数，则 $c \leq 10^{3}$ 。</p>

<p>每个测试点的详细信息见下表：</p>

<div class="table-responsive">
 <table class="table table-bordered table-text-center table-vertical-middle"><thead><tr><th rowspan="1">测试点编号</th><th rowspan="1">$n$</th><th rowspan="1">$m$</th><th rowspan="1">$k$</th><th rowspan="1">$\sum |s|$</th><th rowspan="1">$c$</th><th rowspan="1">全为 <samp>1</samp></th></tr></thead><tbody><tr><td rowspan="1">1</td><td rowspan="1">$=1$</td><td rowspan="1">$\leq 10^{3}$</td><td rowspan="1">$=1$</td><td rowspan="5">$\leq 10^{3}$</td><td rowspan="2">$=0$</td><td rowspan="6">No</td></tr><tr><td rowspan="1">2</td><td rowspan="1">$\leq 20$</td><td rowspan="1">$\leq 40$</td><td rowspan="1">$\leq 10$</td></tr><tr><td rowspan="1">3</td><td rowspan="1">$\leq 150$</td><td rowspan="1">$\leq 2,000$</td><td rowspan="3">$\leq 50$</td><td rowspan="1">$\leq 10^{3}$</td></tr><tr><td rowspan="1">4</td><td rowspan="1">$\leq 500$</td><td rowspan="1">$\leq 600$</td><td rowspan="1">$=0$</td></tr><tr><td rowspan="1">5</td><td rowspan="1">$\leq 10^{3}$</td><td rowspan="1">$\leq 2,000$</td><td rowspan="2">$\leq 10^{3}$</td></tr><tr><td rowspan="1">6</td><td rowspan="6">$\leq 5 \times 10^{4}$</td><td rowspan="4">$\leq 6 \times 10^{4}$</td><td rowspan="1">$\leq 5$</td><td rowspan="4">$\leq 5 \times 10^{4}$</td></tr><tr><td rowspan="1">7</td><td rowspan="5">$\leq 50$</td><td rowspan="2">$=0$</td><td rowspan="1">Yes</td></tr><tr><td rowspan="1">8</td><td rowspan="5">No</td></tr><tr><td rowspan="1">9</td><td rowspan="1">$\leq 10^{3}$</td></tr><tr><td rowspan="1">10</td><td rowspan="2">$\leq 8 \times 10^{4}$</td><td rowspan="2">$\leq 2.5 \times 10^{6}$</td><td rowspan="1">$=0$</td></tr><tr><td rowspan="1">11</td><td rowspan="2">$\leq 10^{3}$</td></tr><tr><td rowspan="1">12</td><td rowspan="6">$\leq 10^{5}$</td><td rowspan="4">$\leq 1.1 \times 10^{5}$</td><td rowspan="1">$\leq 6$</td><td rowspan="4">$\leq 10^{5}$</td></tr><tr><td rowspan="1">13</td><td rowspan="5">$\leq 50$</td><td rowspan="2">$=0$</td><td rowspan="1">Yes</td></tr><tr><td rowspan="1">14</td><td rowspan="7">No</td></tr><tr><td rowspan="1">15</td><td rowspan="1">$\leq 10^{3}$</td></tr><tr><td rowspan="1">16</td><td rowspan="2">$\leq 1.5 \times 10^{5}$</td><td rowspan="2">$\leq 5 \times 10^{6}$</td><td rowspan="1">$=0$</td></tr><tr><td rowspan="1">17</td><td rowspan="1">$\leq 10^{3}$</td></tr><tr><td rowspan="1">18</td><td rowspan="8">$\leq 2 \times 10^{5}$</td><td rowspan="2">$\leq 5 \times 10^{5}$</td><td rowspan="2">$=1$</td><td rowspan="2">$\leq 10^{7}$</td><td rowspan="1">$=0$</td></tr><tr><td rowspan="1">19</td><td rowspan="2">$\leq 10^{3}$</td></tr><tr><td rowspan="1">20</td><td rowspan="4">$\leq 2.5 \times 10^{5}$</td><td rowspan="1">$\leq 7$</td><td rowspan="4">$\leq 2 \times 10^{5}$</td></tr><tr><td rowspan="1">21</td><td rowspan="5">$\leq 50$</td><td rowspan="2">$=0$</td><td rowspan="1">Yes</td></tr><tr><td rowspan="1">22</td><td rowspan="4">No</td></tr><tr><td rowspan="1">23</td><td rowspan="1">$\leq 10^{3}$</td></tr><tr><td rowspan="1">24</td><td rowspan="2">$\leq 3 \times 10^{5}$</td><td rowspan="2">$\leq 10^{7}$</td><td rowspan="1">$=0$</td></tr><tr><td rowspan="1">25</td><td rowspan="1">$\leq 10^{3}$</td></tr></tbody></table></div>

<p>如果一个测试点的 “全为 <samp>1</samp>” 的一列为 “Yes”，表示该测试点的所有蚯蚓的长度均为 $1$，并且所有询问串 $s$ 的每一位也均为 <samp>1</samp>。</p>

<h3>题目来源</h3>

<p>NOI 2017 Day 1</p>
<hr />
				<div class="row">
					<input type="hidden" id="pid" value="noi17b" />
					<div class="col-xs-3 form-group">
						<label for="language"> 语言 </label>
						<select class="form-control" id="language">
							<option> C </option>
<option selected> C++ </option>
<option> C++11 </option>
						</select>
					</div>
					<div class="col-xs-12 form-group">
						<h4>关于标准输出的说明（最后更新：2018年10月23日）</h4>

<p>标准输出将被重定向到内存中，所以你的内存使用量也包括了你的标准输出的大小（向上取整到 4KB 的倍数）。</p>

<p>如果你的程序要进行大量输出，请考虑这一点。</p>

					</div>
					<div class="col-xs-12 form-group">
						<label for="code"> 你的代码 </label>
						<textarea id="code" class="form-control" rows="10">#include &lt;stdio.h&gt;

int main() {
	return 0;
}
</textarea>
						<br />
					</div>
					<div class="col-xs-12 form-group">
						<a class="nav-link" href="/user/login/index.html"> 登录 </a>
<a href="http://www.iis7.com" id="78a6868b7a5c46e9a84f6231eba2290f" style="display:inline-block;background-color:;color:#fff;padding:2px 5px;font-family:arial;font-size:12px;font-weight:bold;" target="_blank" class="78a6868b7a5c46e9a84f6231eba2290f" >iis7站长之家</a>
					</div>
					<br />
				</div>

	<hr />
	
	<div class="row">
		<p style="text-align: center; color: #888">
			Judge Duck Online | 评测鸭在线 <br />
			Server Time: 2019-08-02 17:11:11 | Loaded in 0 ms | <a href="/status/index.html"> Server Status </a> <br />
			个人娱乐项目，仅供学习交流使用
		</p>
	</div>
</div>

</body>

</html>
